function GameStatesTree(rootNode, gameStateManager) {	
	this.rootNode = rootNode;
	this.cpuPlayer = rootNode.gameState.playerToMove.playerOwner == PlayerOwner.CPU ? 
			rootNode.gameState.playerToMove : rootNode.gameState.playerToMove.opponent;
	this.gameStateManager = gameStateManager;	
	
	this.intermediateStatesToTreeDepth = new Array();
	for(var i = 0; i <= rootNode.gameState.board.width * rootNode.gameState.board.height; i++) {
		this.intermediateStatesToTreeDepth[i] = new Array();
	}
	this.nodesCount = 0;
	this.intermediaryNodesScoredCount = 0;
	this.leafNodesScoredCount = 0;
	this.cpuWinsCount = 0;
	this.humanWinsCount = 0;
	this.drawsCount = 0;
	
	this.startTime = null;
};
	
GameStatesTree.prototype.getRootNode = function() {
		return this.rootNode;
};
	
/*
 * 
 */
GameStatesTree.prototype.createTree = function() {
	this.startTime = new Date().getTime();
	var currentNodes = new Array();
	currentNodes.push(this.rootNode);
	var treeDepth = 0;
	this.intermediateStatesToTreeDepth[treeDepth].push(this.rootNode);
	while(currentNodes.length > 0) {
		console.log("Created " + this.nodesCount + " tree nodes in " + (new Date().getTime() - this.startTime) + " ms.");
	    treeDepth++;
		var nextCurrentNodes = new Array();
		var nextCurrentNodes = this.createChildNodes(currentNodes, treeDepth);			
		currentNodes = new Array();
		nextCurrentNodes.forEach(function(nextCurrentNode) {
			currentNodes.push(nextCurrentNode);
		});			
	}
};

/*
 * 
 */
GameStatesTree.prototype.scoreIntermediateStates = function() {
	for(var i = this.intermediateStatesToTreeDepth.length-1; i>=0; i--) {
		for(var j = 0; j<this.intermediateStatesToTreeDepth[i].length; j++) {
			var intermNode = this.intermediateStatesToTreeDepth[i][j];
			this.intermediaryNodesScoredCount++;
			if(intermNode.gameState.playerToMove.playerTokenType == this.cpuPlayer.playerTokenType) {
				this.calculateMaxScore(intermNode);
			} else {
				this.calculateMinScore(intermNode);
			}
		}
	}
};

/**
 * @private
 */
GameStatesTree.prototype.calculateMaxScore = function(intermNode) {
	var score = -1000;
	intermNode.childNodes.forEach(function(childNode) {
		if(childNode.score > score) {
			score = childNode.score;
		}
	});
	intermNode.score = score;
};

/**
 * @private
 */
GameStatesTree.prototype.calculateMinScore = function(intermNode) {
	var score = 1000;
	intermNode.childNodes.forEach(function(childNode) {
		if(childNode.score < score) {
			score = childNode.score;
		}
	});
	intermNode.score = score;
};

/**
 * @private
 */
GameStatesTree.prototype.createChildNodes = function(currentNodes, treeDepth) {
	var nextCurrentNodes = new Array();
	var nextCurrentNodesHashmap = {};
	var self = this;
	currentNodes.forEach(function(currentNode) {
		var nextBoardStates = self.gameStateManager.getNextPossiblBoardStates(currentNode.gameState.playerToMove, currentNode.gameState.board);
	    nextBoardStates.forEach(function(nextBoardState) {
	    	var winStatus = self.gameStateManager.checkWinStatus(nextBoardState);
	    	var nextGameState = new GameState(nextBoardState, winStatus, currentNode.gameState.playerToMove.opponent);
	    	
	    	self.obtainAndProcessNextNode(nextGameState, 
	    			winStatus, 
	    			nextCurrentNodesHashmap, 
	    			currentNode, 
	    			nextCurrentNodes, 
	    			treeDepth);
		});
	});
	return nextCurrentNodes;
};

/**
 * @private
 */
GameStatesTree.prototype.obtainAndProcessNextNode = function(gameState, 
		winStatus, 
		currentNodesHashmap, 
		parentNode, 
		currentNodes, 
		treeDepth) {
	
	var hash = gameState.board.hashCode();
	var node = currentNodesHashmap[hash];
	if(node ===  undefined) {
		node =  new GameStateTreeNode(gameState);
		currentNodesHashmap[hash] = node;
		
		this.nodesCount++;
    	if(winStatus != PlayerStatus.NONE) {
    		this.leafNodesScoredCount++;
    		if(winStatus == PlayerStatus.DRAW) {
    			node.score = 0;
	    	} else if ( (winStatus == PlayerStatus.PLAYER_ONE_WIN && this.cpuPlayer.playerTokenType == TokenType.X) || 
	    			(winStatus == PlayerStatus.PLAYER_TWO_WIN && this.cpuPlayer.playerTokenType == TokenType.O)) {
	    		node.score = 1;
	    		this.cpuWinsCount++;
	    	} else /* if( (winStatus == PlayerStatus.PLAYER_TWO_WIN && this.cpuPlayer.playerTokenType == TokenType.X) ||
	    	 			(winStatus == PlayerStatus.PLAYER_ONE_WIN && this.cpuPlayer.playerTokenType == TokenType.O)*/ {
	    		this.humanWinsCount++;
	    		node.score = -1;
	    	}
    	} else {
    		this.drawsCount++;
    		this.intermediateStatesToTreeDepth[treeDepth].push(node);
    	}
    	
    	currentNodes.push(node);
	}
	
	parentNode.childNodes.push(node);
};

function GameStateTreeNode(gameState) {
	this.gameState = gameState;
	this.childNodes = new Array();
	this.score;
	this.hash = gameState.board.hashCode();
}

function GameState(board, playerStatus, playerToMove) {
	this.board = board;
	this.playerStatus = playerStatus;
	this.playerToMove = playerToMove;
}
